package q413_numberOfArithmeticSlices;

public class Solution_2 {
    /*
    举例 [1, 2, 3, 4, 5, 19, 20, 30, 40] 。答案为7。
    首先容易观察到：
    长度为3的等差数列，可以贡献1种答案。例如 [1,2,3] 。
    长度为4的等差数列，可以贡献3种答案。例如[1,2,3,4]，有长度为3的子数列[1,2,3]和[2,3,4]两种。以及长度为4的数列[1,2,3,4]一种。一共是1+2=3种。
    长度为5的等差数列，可以贡献6种答案。例如[1,2,3,4,5]，有长度为3的子数列[1,2,3]和[2,3,4]和[3,4,5]三种，以及长度为4的子数列[1,2,3,4]和[2,3,4,5]两种，以及长度为5的数列[1,2,3,4,5]一种。一共是1+2+3=6种。
    假设我们已经找到了一个长度为3的等差数列。它可以给答案带来一种贡献。
    如果遍历到下一个数时，发现这个数可以拼接到前面长度为3的等差数列的末尾，形成一个长度为4的等差数列，那么把长度为3的等差数列的答案贡献数加一，就是由于这次拼接带来的新的贡献数。当前长度为4的等差数列，这次拼接新的贡献量为1+1=2。
    同理，下一次遍历又发现一个数可以在已发现的长度为4的等差数列的基础上，拼接成长度为5的等差数列，那么新的贡献量就是2+1=3.
    如果下一个数无法与前面的数列行成新的等差数列，那么贡献量清零。
     */
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return 0;
        }

        int d = nums[0] - nums[1], t = 0;
        int ans = 0;
        // 因为等差数列的长度至少为 3，所以可以从 i=2 开始枚举
        for (int i = 2; i < n; ++i) {
            if (nums[i - 1] - nums[i] == d) {
                ++t;
            } else {
                d = nums[i - 1] - nums[i];
                t = 0;
            }
            ans += t;
        }
        return ans;
    }
}
